public class Test38 {
    //找到k第一次出现的位置
    public static int getFirst(int[] data,int k,int start,int end){
        if (data == null ||data.length == 0 || start > end) return  -1;

        int minIndex = start + (end -start)/2;
        if (minIndex > data.length-1) return minIndex;
        int minData =  data[minIndex];

        if (minData == k){
            if (minIndex > 0 && data[minIndex-1] != k || minIndex == 0) return minIndex;
            else end = minIndex-1;//在前半段寻找
        }
        else  if (minData > k) end = minIndex -1;
        else start = minIndex +1;
        return getFirst(data,k,start,end);
    }

    //找到k最后出现的位置
    public static  int getLast(int[] data,int k,int start,int end){
        if (data == null ||data.length == 0 || start > end) return  -1;
        int minIndex = start + (end -start)/2;
        if (minIndex > data.length-1) return minIndex;
        int minData =  data[minIndex];

        if (minData == k){
            if (minIndex < data.length-1 && data[minIndex+1] != k ||minIndex == data.length-1) return minIndex;
            else start = minIndex+1;
        }else if (minData > k) end = minIndex -1;
        else start = minIndex + 1;
        return getLast(data,k,start,end);
    }

    public static  int getNumberOfK(int[] data,int k){
        int number = 0;
        if (data != null && data.length > 0){
            int first = getFirst(data,k,0,data.length-1);
            int last = getLast(data,k,0,data.length-1);
            if (first > -1 && last > -1 ){
                number = last-first+1;
            }

        }
        return number;
    }

    public static void main(String[] args) {
        // 查找的数字出现在数组的中间
        int[] data1 = {1, 2, 3, 3, 3, 3, 4, 5};
        System.out.println(getNumberOfK(data1, 3)); // 4

        // 查找的数组出现在数组的开头
        int[] data2 = {3, 3, 3, 3, 4, 5};
        System.out.println(getNumberOfK(data2, 3)); // 4

        // 查找的数组出现在数组的结尾
        int[] data3 = {1, 2, 3, 3, 3, 3};
        System.out.println(getNumberOfK(data3, 3)); // 4

        // 查找的数字不存在
        int[] data4 = {1, 3, 3, 3, 3, 4, 5};
        System.out.println(getNumberOfK(data4, 2)); // 0

        // 查找的数字比第一个数字还小，不存在
        int[] data5 = {1, 3, 3, 3, 3, 4, 5};
        System.out.println(getNumberOfK(data5, 0)); // 0

        // 查找的数字比最后一个数字还大，不存在
        int[] data6 = {1, 3, 3, 3, 3, 4, 5};
        System.out.println(getNumberOfK(data6, 0)); // 0

        // 数组中的数字从头到尾都是查找的数字
        int[] data7 = {3, 3, 3, 3};
        System.out.println(getNumberOfK(data7, 3)); // 4

        // 数组中的数字从头到尾只有一个重复的数字，不是查找的数字
        int[] data8 = {3, 3, 3, 3};
        System.out.println(getNumberOfK(data8, 4)); // 0

        // 数组中只有一个数字，是查找的数字
        int[] data9 = {3};
        System.out.println(getNumberOfK(data9, 3)); // 1

        // 数组中只有一个数字，不是查找的数字
        int[] data10 = {3};
        System.out.println(getNumberOfK(data10, 4)); // 0

    }
}
